{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Bit Flips to Convert Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minBitFlips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #转换数字的最少位翻转次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一次 <strong>位翻转</strong>&nbsp;定义为将数字&nbsp;<code>x</code>&nbsp;二进制中的一个位进行 <strong>翻转</strong>&nbsp;操作，即将&nbsp;<code>0</code>&nbsp;变成&nbsp;<code>1</code>&nbsp;，或者将&nbsp;<code>1</code>&nbsp;变成&nbsp;<code>0</code>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>x = 7</code>&nbsp;，二进制表示为&nbsp;<code>111</code>&nbsp;，我们可以选择任意一个位（包含没有显示的前导 0 ）并进行翻转。比方说我们可以翻转最右边一位得到&nbsp;<code>110</code>&nbsp;，或者翻转右边起第二位得到&nbsp;<code>101</code>&nbsp;，或者翻转右边起第五位（这一位是前导 0 ）得到&nbsp;<code>10111</code>&nbsp;等等。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你两个整数&nbsp;<code>start</code> 和&nbsp;<code>goal</code>&nbsp;，请你返回将&nbsp;<code>start</code>&nbsp;转变成&nbsp;<code>goal</code>&nbsp;的&nbsp;<strong>最少位翻转</strong>&nbsp;次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>start = 10, goal = 7\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>10 和 7 的二进制表示分别为 1010 和 0111 。我们可以通过 3 步将 10 转变成 7 ：\n",
    "- 翻转右边起第一位得到：101<strong><em>0</em></strong> -&gt; 101<strong><em>1 。</em></strong>\n",
    "- 翻转右边起第三位：1<strong><em>0</em></strong>11 -&gt; 1<strong><em>1</em></strong>11 。\n",
    "- 翻转右边起第四位：<strong><em>1</em></strong>111 -&gt; <strong><em>0</em></strong>111 。\n",
    "我们无法在 3 步内将 10 转变成 7 。所以我们返回 3 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>start = 3, goal = 4\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>3 和 4 的二进制表示分别为 011 和 100 。我们可以通过 3 步将 3 转变成 4 ：\n",
    "- 翻转右边起第一位：01<strong><em>1</em></strong> -&gt; 01<em><strong>0 </strong></em>。\n",
    "- 翻转右边起第二位：0<strong><em>1</em></strong>0 -&gt; 0<strong><em>0</em></strong>0 。\n",
    "- 翻转右边起第三位：<strong><em>0</em></strong>00 -&gt; <strong><em>1</em></strong>00 。\n",
    "我们无法在 3 步内将 3 变成 4 。所以我们返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= start, goal &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-bit-flips-to-convert-number](https://leetcode.cn/problems/minimum-bit-flips-to-convert-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-bit-flips-to-convert-number](https://leetcode.cn/problems/minimum-bit-flips-to-convert-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10\\n7', '3\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start ^ goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start ^ goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start^goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start ^ goal).count(\"1\")\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return (start ^ goal).bit_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        tmp=bin(start)[2:]\n",
    "        target=bin(goal)[2:]\n",
    "        _max=max(len(tmp),len(target))\n",
    "        tmp=tmp.rjust(_max,\"0\")\n",
    "        target=target.rjust(_max,\"0\")\n",
    "        print(tmp,target)\n",
    "        \n",
    "        return sum([1 for i in range(len(tmp)) if tmp[i]!=target[i]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return (start ^ goal).bit_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        res = 0\n",
    "        tmp = start ^ goal\n",
    "\n",
    "        while tmp:\n",
    "            res += tmp & 1\n",
    "            tmp >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        counts = 0\n",
    "        x = start ^ goal\n",
    "        while x:\n",
    "            counts += x & 1\n",
    "            x >>= 1\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start ^ goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start^goal).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        (b1,b2) = (start,goal) if start > goal else (goal,start)\n",
    "        s1 = bin(b1)[2:][::-1]\n",
    "        s2 = bin(b2)[2:][::-1]\n",
    "        ans = 0\n",
    "        #print(s1,s2)\n",
    "        for i in range(len(s1)):\n",
    "            if i >= len(s2) and s1[i] == \"1\" or i < len(s2) and s1[i] != s2[i]:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start ^ goal).count('1')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        ans = 0 \n",
    "        this = start ^ goal \n",
    "        while this > 0 :\n",
    "            ans += this & 1 \n",
    "            this >>= 1 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        bstart,bgoal = bin(start)[2::],bin(goal)[2::]\n",
    "        max_num = max(len(bstart),len(bgoal))\n",
    "        padded_bstart = f'{bstart:0>{max_num}}'\n",
    "        padded_bgoal = f'{bgoal:0>{max_num}}'\n",
    "        x = 0\n",
    "        for i in range(max_num):\n",
    "            if padded_bstart[i] != padded_bgoal[i]:\n",
    "                x += 1\n",
    "        return x\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        start = bin(start)[2:]\n",
    "        goal = bin(goal)[2:]\n",
    "        if len(start) < len(goal):\n",
    "            start = '0' * (len(goal) - len(start))  + start\n",
    "        else:\n",
    "            goal = '0' * (len(start) - len(goal))  + goal\n",
    "        return sum(start[i]!=goal[i] for i in range(max(len(start), len(goal))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        ans = 0\n",
    "        while start or goal:\n",
    "            if start & 1 != goal & 1:\n",
    "                ans += 1\n",
    "            start >>= 1\n",
    "            goal >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        count = 0\n",
    "        while start != 0 or goal != 0:\n",
    "            if start%2 != goal%2:\n",
    "                count += 1\n",
    "            start = start//2\n",
    "            goal = goal//2\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return (start^goal).bit_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        s1 = f'{start:b}'[::-1]\n",
    "        s2 = f'{goal:b}'[::-1]\n",
    "        return sum(c1 != c2 for c1, c2 in zip_longest(s1, s2, fillvalue = '0'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start ^ goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        res = 0\n",
    "        tmp = start ^ goal\n",
    "        while tmp:\n",
    "            res += tmp & 1\n",
    "            tmp >>= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        bstart,bgoal = bin(start)[2::],bin(goal)[2::]\n",
    "        max_num = max(len(bstart),len(bgoal))\n",
    "        padded_bstart = f'{bstart:0>{max_num}}'\n",
    "        padded_bgoal = f'{bgoal:0>{max_num}}'\n",
    "        x = 0\n",
    "        for i in range(max_num):\n",
    "            if padded_bstart[i] != padded_bgoal[i]:\n",
    "                x += 1\n",
    "        return x\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        ans = 0\n",
    "        while start and goal:\n",
    "            if (start & 1) != (goal & 1):\n",
    "                ans += 1\n",
    "            start >>= 1\n",
    "            goal >>= 1\n",
    "        return ans + bin(start).count('1') + bin(goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        result = 0\n",
    "        xor_result = start ^ goal  # 使用异或运算获取不同位\n",
    "        while xor_result:\n",
    "            result += xor_result & 1  # 检查最低位是否为1\n",
    "            xor_result >>= 1  # 右移一位，检查下一位\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        ret = start ^ goal\n",
    "        ans = 0\n",
    "        while (ret):\n",
    "            ans += ret & 1\n",
    "            ret >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "         return bin(start ^ goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return (bin(start^goal)).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        n = start ^ goal\n",
    "        result = 0\n",
    "\n",
    "        while n > 0:\n",
    "            result += 1 & n\n",
    "            n >>= 1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        s='{:064b}'.format(start)\n",
    "        t='{:064b}'.format(goal)        \n",
    "        count=0\n",
    "        #print(s)\n",
    "        #print(t)\n",
    "        for i in range(len(s)):            \n",
    "            if s[i]!=t[i]:\n",
    "                count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        ans = 0 \n",
    "        this = start ^ goal \n",
    "        while this > 0 :\n",
    "            if this & 1 > 0 :\n",
    "                ans += 1 \n",
    "            this >>= 1 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        res=0\n",
    "        tmp=start^goal\n",
    "        while tmp:\n",
    "            res+=tmp&1\n",
    "            tmp>>=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        n = start^goal\n",
    "        ans = 0\n",
    "        while n:\n",
    "            ans+=n%2\n",
    "            n//=2\n",
    "        return ans\n",
    "        return sum([i%2 for i in bin(start^goal)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        a = bin(start)[2:].zfill(128)\n",
    "        b = bin(goal)[2:].zfill(128)\n",
    "        return sum(1 for i in range(128) if a[i] != b[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        res = 0\n",
    "        tmp =start ^ goal\n",
    "        while tmp:\n",
    "            res += tmp & 1\n",
    "            tmp>>=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start^goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start, goal):\n",
    "        \"\"\"\n",
    "        \n",
    "        \n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if start == None or goal == None:\n",
    "            return -1 \n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        #由于start, goal都小于1e9, 将其都视作32位的整数, 遍历32位每一位的异同\n",
    "        for i in range(32):\n",
    "            pos_1 = 1 << i \n",
    "            ans += (((start ^ goal) & pos_1) != 0)\n",
    "\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return sum([int(i)%2 for i in bin(start^goal)[2:]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "      res = 0\n",
    "      tmp = start ^ goal\n",
    "      while tmp:\n",
    "        res += tmp & 1\n",
    "        tmp >>= 1\n",
    "      return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minBitFlips(self, start: int, goal: int) -> int:\n",
    "#         res=0\n",
    "#         while goal: ### 逐位比较（有点蠢，用异或就好）\n",
    "#             if start&1!=goal&1:\n",
    "#                 res+=1\n",
    "#             start>>=1\n",
    "#             goal>>=1\n",
    "#         while start:### 剩余未比较完的数字\n",
    "#             res+=1\n",
    "#             start=start&(start-1)\n",
    "#         return res\n",
    "\n",
    "# ### 官解法：位运算+统计1个数\n",
    "# class Solution:\n",
    "#     def minBitFlips(self,start,goal):\n",
    "#         cmp=start^goal\n",
    "#         res=0\n",
    "#         while cmp: ### way1:统计1的个数\n",
    "#             res+=cmp&1\n",
    "#             cmp>>=1\n",
    "#         return res\n",
    "\n",
    "### 官解法：位运算+统计1个数\n",
    "class Solution:\n",
    "    def minBitFlips(self,start,goal):\n",
    "        cmp=start^goal\n",
    "        res=0\n",
    "        while cmp: ### way2：统计1的个数\n",
    "            res+=1\n",
    "            cmp&=cmp-1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start^goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start^goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        # s=bin(start)[2:]\n",
    "        # g=bin(goal)[2:]\n",
    "        # print(bin(start^goal))\n",
    "        return bin(start^goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start ^ goal).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        x = start^goal\n",
    "        s = bin(x)[2:]\n",
    "        cnt = Counter(s)\n",
    "        return cnt['1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        res1 = bin(start)[2:][::-1]\n",
    "        res2 = bin(goal)[2:][::-1]\n",
    "        n = len(res1)\n",
    "        m = len(res2)\n",
    "        count = 0\n",
    "        for j in range(min(n,m)):\n",
    "            if res1[j] != res2[j]:\n",
    "                count += 1\n",
    "        if n > m:\n",
    "            for i in range(m,n):\n",
    "                if res1[i] == '1':\n",
    "                    count += 1\n",
    "        elif n < m:\n",
    "            for i in range(n,m):\n",
    "                if res2[i] == '1':\n",
    "                    count += 1\n",
    "        \n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        n = start ^ goal\n",
    "        result = 0\n",
    "\n",
    "        while n > 0:\n",
    "            result += 1 & n\n",
    "            n >>= 1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        a = bin(start)[2:]\n",
    "        b = bin(goal)[2:]\n",
    "        m , n = len(a) ,len(b)\n",
    "        r = abs(m-n)\n",
    "        res = 0\n",
    "        if m > n:\n",
    "            a1 = a[:r]\n",
    "            a = a[r:]\n",
    "            for j in a1:\n",
    "                if j =='1':\n",
    "                    res += 1\n",
    "        if m < n:\n",
    "            b1 = b[:r]\n",
    "            b = b[r:]\n",
    "            for j in b1:\n",
    "                if j =='1':\n",
    "                    res += 1\n",
    "        for i in range(min(m,n)):\n",
    "            if a[i] != b[i]:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        digits = start^goal\n",
    "        count = 0\n",
    "        while digits > 0:\n",
    "            if digits&1:\n",
    "                count += 1\n",
    "            digits >>= 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        t = start ^ goal\n",
    "        return t.bit_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        n=start^goal\n",
    "        cnt=0\n",
    "        while n:\n",
    "            cnt=cnt+1\n",
    "            n&=n-1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(32, -1, -1):\n",
    "            ans += (start >> i & 1) != (goal >> i & 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        bstart,bgoal = bin(start)[2::],bin(goal)[2::]\n",
    "        max_num = max(len(bstart),len(bgoal))\n",
    "        padded_bstart = f'{bstart:0>{max_num}}'\n",
    "        padded_bgoal = f'{bgoal:0>{max_num}}'\n",
    "        x = 0\n",
    "        for i in range(max_num):\n",
    "            if padded_bstart[i] != padded_bgoal[i]:\n",
    "                x += 1\n",
    "        return x\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        a = bin(start)[2:]\n",
    "        b = bin(goal)[2:]\n",
    "        if len(a)>len(b):\n",
    "            b = '0'*(len(a)-len(b)) + b\n",
    "        else:\n",
    "            a = '0'*(len(b)-len(a)) + a\n",
    "        c = 0\n",
    "        for i in range(len(a)):\n",
    "            if a[i] != b[i]:\n",
    "                c+=1\n",
    "        return c\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return (start ^ goal).bit_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        n = start^goal\n",
    "        ans = 0\n",
    "        while n:\n",
    "            ans+=n%2\n",
    "            n//=2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        cnt=[[0]*2 for _ in range(30)]\n",
    "        res=0\n",
    "        for i in range(30):\n",
    "            if (goal>>i&1)!= (start>>i&1):\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start ^ goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        res=0\n",
    "        while goal:\n",
    "            if start&1!=goal&1:\n",
    "                res+=1\n",
    "            start>>=1\n",
    "            goal>>=1\n",
    "        while start:\n",
    "            res+=1\n",
    "            start=start&(start-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        n=max(start.bit_length(),goal.bit_length())\n",
    "        print(n)\n",
    "        ret=0\n",
    "        for i in range(n):\n",
    "            if (start>>i &1)^(goal>>i&1):\n",
    "                ret+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        def ten2TwoReversed(num):\n",
    "            res = []\n",
    "            while num:\n",
    "                res.append(str(num % 2))\n",
    "                num = num // 2\n",
    "            # res = res[::-1]\n",
    "            return \"\".join(res)\n",
    "        def countOnes(num):\n",
    "            cnt = 0\n",
    "            for n in num:\n",
    "                if n == \"1\":\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "        if not start and not goal:\n",
    "            return 0\n",
    "        if not start:\n",
    "            return countOnes(list(ten2TwoReversed(goal)))\n",
    "        if not goal:\n",
    "            return countOnes(list(ten2TwoReversed(start)))\n",
    "        start = ten2TwoReversed(start)\n",
    "        goal = ten2TwoReversed(goal)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        count = 0\n",
    "        while i <= len(start) - 1 and j <= len(goal) - 1:\n",
    "            if start[i] != goal[j]:\n",
    "                count += 1\n",
    "            i += 1\n",
    "            j += 1\n",
    "        if len(start) > len(goal):\n",
    "            count = count + countOnes(start[len(goal):])\n",
    "        elif len(start) < len(goal):\n",
    "            count = count + countOnes(goal[len(start):])\n",
    "        return count\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(bin(start)) - len(bin(goal))\n",
    "        s1 = bin(start)[2:]\n",
    "        s2 = bin(goal)[2:]\n",
    "        print(s1,s2)\n",
    "        if n >= 0:\n",
    "            s = n * '0'\n",
    "            s2 = s + s2\n",
    "        else:\n",
    "            s = n*(-1)*'0'\n",
    "            s1 = s + s1\n",
    "        print(s1,s2)\n",
    "        for i in range(0,len(s1)):\n",
    "            if s1[i] != s2[i]:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        # s=bin(start)[2:]\n",
    "        # g=bin(goal)[2:]\n",
    "        # print(bin(start^goal))\n",
    "        return bin(start^goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        # res = 0\n",
    "        # tmp = start ^ goal\n",
    "        # while tmp:\n",
    "        #     res += tmp & 1\n",
    "        #     tmp >>= 1\n",
    "        # return res\n",
    "        return bin(start^goal).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        x = 0\n",
    "        while start or goal:\n",
    "            if start&1 != goal&1:\n",
    "                x += 1\n",
    "            start >>= 1\n",
    "            goal >>= 1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        n = start^goal\n",
    "        ans = 0\n",
    "        while n:\n",
    "            ans+=n%2\n",
    "            n//=2\n",
    "        return ans\n",
    "        return sum([i%2 for i in bin(start^goal)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minBitFlips(self, start: int, goal: int) -> int:\n",
    "        return bin(start ^ goal).count(\"1\")"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
